package com.cat.greedyAlgorithm;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/
 * @create 2025/10/9 19:35
 * @since JDK17
 */

public class Solution68 {
    class Emp {
        double ratio;
        int quality;

        public Emp(double ratio, int quality) {
            this.ratio = ratio;
            this.quality = quality;
        }
    }

    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Emp[] emp = new Emp[n];
        for (int i = 0; i < n; i++) {
            emp[i] = new Emp((double) wage[i] / quality[i], quality[i]);
        }
        Arrays.sort(emp, (a, b) -> Double.compare(a.ratio, b.ratio));
        double ans = Double.MAX_VALUE;
        int sum = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0, cur; i < n; i++) {
            cur = emp[i].quality;
            if (heap.size() < k) {
                sum += cur;
                heap.add(cur);
                if (heap.size() == k) { // 已经有k个了
                    ans = Math.min(ans, sum * emp[i].ratio);
                }
            } else {    //
                if (heap.peek() > cur) {
                    sum -= heap.poll() - cur;
                    heap.add(cur);
                    ans = Math.min(ans, sum * emp[i].ratio);
                }
            }
        }

        return ans;
    }
}
